package com.zxkfeel.string;

import java.util.HashMap;
import java.util.Map;

/**
 * 3.title:无重复字符的最长子串
 * 给定一个字符串，找出不含有重复字符的最长子串的长度。
 * 示例：给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
 * 给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
 * 给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列  而不是子串。
 */
public class StringCode3 {

    public static void main(String[] args) {
        String s = "";
        int a = lengthOfLongestSubstring(s);
        System.out.println(a);
    }

    public static int lengthOfLongestSubstring(String s) {
        if(s.length()<1){
            return 0;
        }
        //charPosition统计s中每种字符之前出现的位置
        Map<Character, Integer> charPosition = new HashMap<Character, Integer>();
        //preArr代表以s[i-1]结尾的情况下，最长无重复子串的长度
        int[] preArr = new int[s.length()];
        char[] str2charArr = s.toCharArray();
        //从头到尾遍历str2charArr，统计出以每个字符为当前位置的向前最长无重复子串的长度
        for(int i=0; i<s.length(); i++){
            Integer lastPosOfChar = charPosition.get(str2charArr[i]);
            if(lastPosOfChar == null){//说明当前字符第一次出现
                //更新最长无重复子串的长度
                preArr[i] = i == 0 ? 1 : preArr[i-1] + 1;
                //记录当前字符出现的位置
                charPosition.put(str2charArr[i], i);
            }
            else{//当前字符不是第一次出现(既然不是第一次出现，那也不是在第一个位置),也就是之前出现过该字符
                //获取前一个字符最长无重复子串的长度
                int aPos = lastPosOfChar + 1;
                int unRepeatLen = preArr[i-1];
                int bPos = i - unRepeatLen;
                if(aPos >= bPos){
                    //当前位置的最长无重复子串长度
                    preArr[i] = i - aPos + 1;
                }
                else{
                    //当前位置的最长无重复子串长度
                    preArr[i] = i - bPos + 1;
                }
                //跟新当前字符出现的位置
                charPosition.put(str2charArr[i], i);
            }
        }
        //遍历preArr,最大值即为所求
        int max = preArr[0];
        for(int i: preArr) if(i > max) max = i;
        return max;
    }

    /**
     * 用时最短的方法
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s) {

        int max=0;
        int count=0;

        char[] c=s.toCharArray();
        for(int i=0;i<c.length;i++){
            for(int j=count;j<i;j++){
                if(c[i]==c[j]){
                    count=j+1;
                    break;
                }
            }
            max=Math.max(max,i-count+1);
        }
        return max;
    }
}
